/*
 * sorted link list manipulation
 * - insert
 *    1) insert at the beginning
 *    2) insert in the middle
 *    3) insert at the end
 * - reverse
 *    1) need 3 pointers
 *    2) need to return the new head pointer
 *    3) do not forget to set the tail to NULL
 * - print
 * - destory
 */
#include <stdio.h>
#include <stdlib.h>


typedef struct node_ {
    struct node_ *next;
    int val;
} node;


void list_insert (node **head, int a)
{
    node *p, *cur, *prev;

    p = (node*)malloc(sizeof(node));
    p->next = NULL;
    p->val = a;

    if (*head == NULL) {
        /* the list has not been initialized */
        *head = p;
        return;
    }

    prev = cur = *head;
    while (cur->val <= p->val && cur->next) {
        prev = cur;
        cur = cur->next;
    }

    if (p->val < cur->val) {
        if (cur == *head) {
            /* insert at the beginning */
            p->next = cur;
            *head = p;
        } else {
            /* insert at the middle */
            prev->next = p;
            p->next = cur;
        }
    } else {
        /* insert at the end */
        cur->next = p;
        p-> next = NULL;
    }
}

void list_reverse (node **head)
{
    node *p1, *p2, *p3;

    if (*head == NULL || (*head)->next == NULL) {
        return;
    }
    
    p1 = *head;
    p2 = p1->next;
    while (p2) {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    (*head)->next = NULL;
    
    *head = p1;
}

void list_destroy (node **head)
{
    node *cur, *next;

    cur = *head;
    while (cur) {
        next = cur->next;
        free(cur);
        cur = next;
    }

    *head = NULL;
}

node* list_find_kth_to_tail (node *head, unsigned int k)
{
    int i = 0;
    node *p1, *p2;
    
    if (head == NULL) {
        return NULL;
    }

    p1 = head;
    for (i=0; i<k; i++) {
        p1 = p1->next;
        if (p1 == NULL) {
            return NULL;
        }
    }

    p2 = head;
    while (p1 != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }

    return p2;
}

void list_print (node *head) 
{
    node *p = head;
    
    printf(">>> list: ");
    while (p) {
        printf(" %d ", p->val);
        p = p->next;
    }
    printf("\n");
}

int main(int argc, char *argv[])
{
    node *head = NULL;
    node *p = NULL;
    
    list_insert(&head, 7);
    list_insert(&head, 2);
    list_insert(&head, 5);
    list_insert(&head, 1);
    list_insert(&head, 2);

    list_print(head);

    p = list_find_kth_to_tail(head, 2);
    if (p) {
        printf("The last 2 node is %d\n", p->val);
    }

    list_reverse(&head);
    list_print(head);
    list_destroy(&head);
    
    return 0;
}
